package problem397;

//379.整数替换
//https://leetcode.cn/problems/integer-replacement/description/

class Solution2 {
    public int integerReplacement(int n) {
        int ret = 0;
        while(n != 1) {
            if(n % 2 == 0) {
                n /= 2;
                ret ++;
            }else {
                if(n == 3) {
                    ret += 2;
                    n = 1;
                }else if(n % 4 == 1) {
                    n = n/2;
                    ret += 2;
                }else {
                    n = n/2 + 1;
                    ret += 2;
                }
            }
        }
        return ret;
    }
}